package com.hy;

import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2024/8/23
 * Time:00:52
 */
public class MinWindow {

    /**
     * 寻找字符串s中能覆盖字符串t所有字符的最小子串
     * @param s 源字符串
     * @param t 需要被覆盖的字符串
     * @return 返回满足条件的最小子串，如果不存在返回空字符串
     */
    public String minWindow(String s, String t) {
        // s和t的长度
        int m = s.length(), n = t.length();
        // 如果s的长度小于t，直接返回空字符串，因为无法覆盖t的所有字符
        if(m < n) return "";

        // 初始化左右指针和结果变量
        int l = 0, r = 0;
        // resL和resR用于记录满足条件的子串的左右索引，初始值表示无有效子串
        int resL = -1, resR = m;

        // numsS和numsT用于记录s和t中字符出现的次数
        int[] numsS = new int[128];
        int[] numsT = new int[128];

        // 统计t中每个字符出现的次数
        for(int i = 0; i < n; i++){
            numsT[t.charAt(i)]++;
        }

        // 使用滑动窗口遍历s字符串
        while(r < m){
            // 将当前字符加入窗口
            numsS[s.charAt(r++)]++;

            // 当窗口覆盖了t的所有字符时，尝试缩小窗口并更新最小子串
            while(isCovered(numsS, numsT)){
                // 如果当前窗口更小，则更新最小子串的索引
                if(r - l < resR - resL){
                    resL = l;
                    resR = r;
                }
                // 左指针向右移动，缩小窗口
                numsS[s.charAt(l++)]--;
            }
        }

        // 根据最小子串的索引返回结果，如果resL仍然是-1，表示无有效子串
        return resL == -1? "" : s.substring(resL, resR);
    }

    private boolean isCovered(int[] numsR, int[] numsT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (numsR[i] < numsT[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (numsR[i] < numsT[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        MinWindow minWindow = new MinWindow();
        System.out.println(minWindow.minWindow("a", "a"));
    }
}
